一道腾讯面试题，击败100%的用户，合并排序链表

作者丨小夕

来源丨公众号：小夕学算法（ID：gh_a73f3afde197）

题目

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4 限制：

0 <= 链表长度 <= 1000

注意：本题与主站 21 题相同：https://leetcode-cn.com/problems/merge-two-sorted-lists/

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

文字思路

• 设置dummy为哑结点，放置于新链表之前，最后返回的就是dummy.next；设置cur为当前节点，从dummy开始
• 当两个链表都非空时进入循环，令新链表的下一个节点cur.next为val更小的节点，相应的链表节点后移一位
• 每次循环记得cur也要后移一位
• 如果循环结束后还有链表非空，cur指向非空链表
• 返回dummy.next

图解思路

上述图片中的文字：

• 创建一个伪头结点 tempHead 节点 cur 指向 tempHead 节点 接下来比较 head1 和 head2 两个链表 哪个节点小 就把 tempHead 指向谁
• head1.val >= head2.val 所以 head2 节点是值较小的，让cur.next指向head2节点
• cur.next指向了head2，如图所示，接着让head2 = head2.next，让head2 继续参与接下来的比较。
• 完成了cur.next 指向了head2，head2 = head2.next，接下来让 cur指向下一个节点 cur = cur.next
• 完成了cur.next指向了head2，head2 = head2.next，cur = cur.next变成了如图所示。
• 接着继续重复上述过程 继续比较 head1.val < head2.val
• 由于 head1.val < head2.val 继续执行之前的三步：cur.next = head1 head1 = head1.next cur = cur.next
• 由于 head1.val < head2.val 继续执行之前的三步：cur.next = head1 head1 = head1.next cur = cur.next 执行完这三步以后，如图所示。
• 接下来继续比较head1.val和head2.val 因为 head1.val < head2.val 继续执行之前的三步：cur.next = head1 head1 = head1.next cur = cur.next
• cur.next = head1 head1 = head1.next cur = cur.next如图所示
• 接下来继续比较head1.val和 head2.val 因为 head1.val > head2.val：所以执行 cur.next = head2 head2 = head2.next cur = cur.next
• 接下来继续比较head1.val和 head2.val 因为 head1.val >= head2.val：所以继续执行 cur.next = head2 head2 = head2.next cur = cur.next
• 执行完如图所示，head1指向了null，所以排序列表一遍历结束了，所以把排序列表二接到合并排序列表后面。
• 接到后面，cur.next = head2 完成全部排序。
• 由于需要返回1-1-2-3-4-4 所以最后返回tempHead.next 节点

动画

本文原创作者：小夕，一名BAT大厂程序媛。
文章首发平台：微信公众号【小夕学算法】。

点分享

点点赞

点在看